/*
 * @lc app=leetcode.cn id=37 lang=golang
 *
 * [37] 解数独
 */

// @lc code=start

/*
三步走：
1. 找到需要填充数字的位置
loop： 遍历位置信息，知道最后一个位置被填写
	2. 找到此位置可以填充的数字
	3. 使用 回溯法 填写数字
*/
type node struct {
	X, Y int
}

func solveSudoku(board [][]byte) {
	m, n := len(board), len(board[0])
	isempty := make([]node, 0, m*n)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == '.' {
				isempty = append(isempty, node{i, j})
			}
		}
	}
	// fmt.Println(search(isempty[0], m, n, board))

	var backing func(pos int) bool
	backing = func(pos int) bool {
		if pos >= len(isempty) {
			return true
		}
		nd := isempty[pos]
		rt := search(nd, m, n, board)
		for i := 0; i < len(rt); i++ {
			board[nd.X][nd.Y] = byte(int('0') + rt[i])
			t := backing(pos + 1)
			if t {
				return true
			}
			board[nd.X][nd.Y] = '.'
		}
		return false
	}
	backing(0)

}

func search(nd node, m, n int, board [][]byte) []int {
	res := make([]int, 9)
	for j := 0; j < n; j++ {
		if j == nd.Y || board[nd.X][j] == '.' {
			continue
		}
		res[board[nd.X][j]-'0'-1] = 1
	}
	for i := 0; i < m; i++ {
		if i == nd.X || board[i][nd.Y] == '.' {
			continue
		}
		res[board[i][nd.Y]-'0'-1] = 1
	}
	i, j := (nd.X/3)*3, (nd.Y / 3 * 3)
	for a := i; a < i+3; a++ {
		for b := j; b < j+3; b++ {
			if board[a][b] == '.' {
				continue
			}
			res[board[a][b]-'0'-1] = 1
		}
	}
	tr := make([]int, 0, 9)
	for a := 0; a < len(res); a++ {
		if res[a] == 1 {
			continue
		}
		tr = append(tr, a+1)
	}
	return tr

}

// @lc code=end

